{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number Of Corner Rectangles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countCornerRectangles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #角矩形的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个只包含 <code>0</code> 和 <code>1</code> 的&nbsp;<code>m x n</code>&nbsp;整数矩阵&nbsp;<code>grid</code>&nbsp;，返回 <em>其中 「<strong>角矩形 」</strong>的数量</em> 。</p>\n",
    "\n",
    "<p>一个<strong>「角矩形」</strong>是由四个不同的在矩阵上的 <code>1</code> 形成的&nbsp;<strong>轴对齐&nbsp;</strong>的矩形。注意只有角的位置才需要为 <code>1</code>。</p>\n",
    "\n",
    "<p><strong>注意：</strong>4 个 <code>1</code>&nbsp;的位置需要是不同的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/12/cornerrec1-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>只有一个角矩形，角的位置为 grid[1][2], grid[1][4], grid[3][2], grid[3][4]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/12/cornerrec2-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1],[1,1,1],[1,1,1]]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>这里有 4 个 2x2 的矩形，4 个 2x3 和 3x2 的矩形和 1 个 3x3&nbsp;的矩形。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/12/cornerrec3-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1,1]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>矩形必须有 4 个不同的角。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;不是&nbsp;<code>0</code>&nbsp;就是&nbsp;<code>1</code></li>\n",
    "\t<li>网格中&nbsp;<code>1</code>&nbsp;的个数在&nbsp;<code>[1, 6000]</code> 范围内</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-corner-rectangles](https://leetcode.cn/problems/number-of-corner-rectangles/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-corner-rectangles](https://leetcode.cn/problems/number-of-corner-rectangles/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]', '[[1,1,1],[1,1,1],[1,1,1]]', '[[1,1,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        #固定一段,求另一端的解法\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(i+1,m):\n",
    "                #枚举两行\n",
    "                #再计算这两行中对应列同时为1的个数\n",
    "                cnt=0\n",
    "                for k in range(n):\n",
    "                    if grid[i][k]==1 and grid[j][k]==1:\n",
    "                        cnt+=1\n",
    "                ans+=(cnt-1)*cnt//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                cnt = 0\n",
    "                for k in range(n):\n",
    "                    if grid[i][k] + grid[j][k] == 2:\n",
    "                        cnt += 1\n",
    "                ans += cnt * (cnt - 1) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        if m ==1 or n==1:\n",
    "            return 0 \n",
    "        # 用dp[i][j]记从第一行到当前行grid[k][i]==grid[k][j]==1的k的个数cnt\n",
    "        # 则要求的总数就是遍历所有的i、j组合，求(cnt-1)*cnt//2的个数\n",
    "        # 而dp的更新递推关系为：dp[i][j] +=(grid[k][i]==grid[k][j]==1)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        # print(\"dp:\",dp)\n",
    "        for k in range(m):\n",
    "            for i in range(n-1):\n",
    "                for j in range(i+1,n):\n",
    "                    dp[i][j] += (grid[k][i]==grid[k][j]==1)\n",
    "        ans = 0 \n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                ans += (dp[i][j]-1)*dp[i][j] //2\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        #固定一段,求另一端的解法\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(i+1,m):\n",
    "                #枚举两行\n",
    "                #再计算这两行中对应列同时为1的个数\n",
    "                cnt=0\n",
    "                for k in range(n):\n",
    "                    if grid[i][k]==1 and grid[j][k]==1:\n",
    "                        cnt+=1\n",
    "                ans+=(cnt-1)*cnt//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid[0])\n",
    "        m = len(grid)\n",
    "        self.ret =0\n",
    "        def checkPoint(i, j):\n",
    "            for ni in range(i+1, m):\n",
    "                if grid[ni][j] == 1:\n",
    "                    for nj in range(j+1, n):\n",
    "                        if grid[i][nj] == 1 and grid[ni][nj] == 1:\n",
    "                            self.ret +=1\n",
    "        for i in range(m-1):\n",
    "            for j in range(n-1):\n",
    "                if grid[i][j] == 1:\n",
    "                    checkPoint(i, j)\n",
    "        return self.ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 用dp[i][j]记从第一行到当前行grid[k][i]==grid[k][j]==1的k的个数cnt。\n",
    "# 则要求的总数就是遍历所有的i、j组合，求(cnt-1)*cnt//2的和\n",
    "# 而dp的更新递推关系为：dp[i][j]+=(grid[k][i]==grid[k][j]==1)\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "      m, n  = len(grid), len(grid[0])\n",
    "      if m == 0 or n == 0: return 0\n",
    "      dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "      for k in range(m): # row\n",
    "        # 先找到所有使得grid[k][p]==1的下标p，记入candidates列表，再对列表中的组合做更新即可\n",
    "        candidates = [p for p in range(n) if grid[k][p]]\n",
    "        for i in range(len(candidates) - 1):\n",
    "          for j in range(i + 1, len(candidates)):\n",
    "            dp[candidates[i]][candidates[j]] += 1\n",
    "\n",
    "      res = 0\n",
    "      for i in range(n-1):\n",
    "        for j in range(i+1, n):\n",
    "          res += (dp[i][j] - 1) * dp[i][j] / 2 # 组合: dp[i][j]中选两个\n",
    "      return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        if m ==1 or n==1:\n",
    "            return 0 \n",
    "        # 用dp[i][j]记从第一行到当前行grid[k][i]==grid[k][j]==1的k的个数cnt\n",
    "        # 则要求的总数就是遍历所有的i、j组合，求(cnt-1)*cnt//2的个数\n",
    "        # 而dp的更新递推关系为：dp[i][j] +=(grid[k][i]==grid[k][j]==1)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        # print(\"dp:\",dp)\n",
    "        for k in range(m):\n",
    "            for i in range(n-1):\n",
    "                for j in range(i+1,n):\n",
    "                    dp[i][j] += (grid[k][i]==grid[k][j]==1)\n",
    "        ans = 0 \n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                ans += (dp[i][j]-1)*dp[i][j] //2\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for r in range(m):\n",
    "            candidates = [col for col in range(n) if grid[r][col]]\n",
    "            l = len(candidates)\n",
    "            for i in range(l - 1):\n",
    "                for j in range(i + 1, l):\n",
    "                    dp[candidates[i]][candidates[j]] += 1\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                res += (dp[i][j] - 1) * dp[i][j] // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        count = 0\n",
    "\n",
    "\n",
    "        for row1 in range(rows - 1):\n",
    "            for row2 in range(row1 + 1, rows):\n",
    "\n",
    "                pairs = 0\n",
    "                for col in range(cols):\n",
    "                    if grid[row1][col] == 1 and grid[row2][col] == 1:\n",
    "                        pairs += 1\n",
    "\n",
    "                count += pairs * (pairs - 1) // 2\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        cnt_1 = 0\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                for k in range(n):\n",
    "                    if grid[i][k] == grid[j][k] == 1:\n",
    "                        cnt_1 += 1\n",
    "                if cnt_1 >= 2:\n",
    "                    res += cnt_1 * (cnt_1 - 1) // 2\n",
    "                cnt_1 = 0\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(m - 1):\n",
    "            for j in range(i + 1, m):\n",
    "                count = 0\n",
    "                for k in range(n):\n",
    "                    if grid[i][k] == grid[j][k] == 1:\n",
    "                        count += 1\n",
    "                res += (count - 1) * count // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    for k in range(j + 1, n):\n",
    "                        if grid[i][k] == 1:\n",
    "                            res += dp[j][k]\n",
    "                            dp[j][k] += 1\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, g: List[List[int]]) -> int:\n",
    "        n, dp = 0, [[0 for i in range(200)] for i in range(200)]\n",
    "        for i in range(len(g)):\n",
    "            for j in range(len(g[i])):\n",
    "                if g[i][j]:\n",
    "                    for k in range(j + 1, len(g[i])):\n",
    "                        if g[i][k]:\n",
    "                            n += dp[j][k]\n",
    "                            dp[j][k] += 1\n",
    "\n",
    "        return n\n",
    "        \n",
    "    \n",
    "    def countCornerRectangles2(self, grid: List[List[int]]) -> int:\n",
    "        count = collections.Counter()\n",
    "        ans = 0\n",
    "        for row in grid:\n",
    "            for c1, v1 in enumerate(row):\n",
    "                if v1:\n",
    "                    for c2 in xrange(c1+1, len(row)):\n",
    "                        if row[c2]:\n",
    "                            ans += count[c1, c2]\n",
    "                            count[c1, c2] += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "    def countCornerRectangles3(self, g: List[List[int]]) -> int:\n",
    "        idxv = [[] for i in range(len(g))]\n",
    "        map = [[0 for i in range(200)] for i in range(200)]\n",
    "        \n",
    "        for i in range(len(g)):\n",
    "            for j in range(len(g[i])):\n",
    "                if g[i][j]:\n",
    "                    idxv[i].append(j)\n",
    "                    map[i][j] = 1\n",
    "        n = 0\n",
    "        for i in range(len(g)):\n",
    "            for j in range(i + 1, len(g)):\n",
    "                t = 0\n",
    "                for k in range(len(idxv[i])):\n",
    "                    if map[j][idxv[i][k]]:\n",
    "                        t += 1\n",
    "                n += t * (t - 1) >> 1\n",
    "\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countCornerRectangles(self, grid):\n",
    "        count = collections.Counter()\n",
    "        ans = 0\n",
    "        for row in grid:\n",
    "            for c1, v1 in enumerate(row):\n",
    "                if v1:\n",
    "                    for c2 in range(c1+1, len(row)):\n",
    "                        if row[c2]:\n",
    "                            ans += count[c1, c2]\n",
    "                            count[c1, c2] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countCornerRectangles(self, grid):\n",
    "        count = collections.Counter()\n",
    "        ans = 0\n",
    "        for row in grid:\n",
    "            for c1, v1 in enumerate(row):\n",
    "                if v1:\n",
    "                    for c2 in range(c1+1, len(row)):\n",
    "                        if row[c2]:\n",
    "                            ans += count[c1, c2]\n",
    "                            count[c1, c2] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pairs = {}\n",
    "        count = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j1 in range(n):\n",
    "                if grid[i][j1] == 1:\n",
    "                    for j2 in range(j1 + 1, n):\n",
    "                        if grid[i][j2] == 1:\n",
    "                            if(j1, j2) in pairs:\n",
    "                                count += pairs[(j1, j2)]\n",
    "                                pairs[(j1, j2)] += 1\n",
    "                            else:\n",
    "                                pairs[(j1, j2)] = 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCornerRectangles(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        d = defaultdict(int)\n",
    "        for row in range(m):\n",
    "            for i in range(n - 1):\n",
    "                for j in range(i + 1,n):\n",
    "                    if grid[row][i] and grid[row][j]:\n",
    "                        d[(i,j)] += 1 \n",
    "        return sum([x*(x - 1) // 2 for x in d.values()])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countCornerRectangles(self, grid):\n",
    "        rows = [[c for c, val in enumerate(row) if val]\n",
    "                for row in grid]\n",
    "        N = sum(len(row) for row in grid)\n",
    "        SQRTN = int(N**.5)\n",
    "\n",
    "        ans = 0\n",
    "        count = collections.Counter()\n",
    "        for r, row in enumerate(rows):\n",
    "            if len(row) >= SQRTN:\n",
    "                target = set(row)\n",
    "                for r2, row2 in enumerate(rows):\n",
    "                    if r2 <= r and len(row2) >= SQRTN:\n",
    "                        continue\n",
    "                    found = sum(1 for c2 in row2 if c2 in target)\n",
    "                    ans += found * (found - 1) / 2\n",
    "            else:\n",
    "                for pair in itertools.combinations(row, 2):\n",
    "                    ans += count[pair]\n",
    "                    count[pair] += 1\n",
    "\n",
    "        return int(ans)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
